package test.algorithm.FastSlowPointer;

/**
 * 二叉排序树
 * @author serenity
 *
 */
public class BinarySortTree {
	
	class BiTNode{
		public int data;
		
		public BiTNode lChild;
		
		public BiTNode rChild;
		
	}
	
	/**
	 * 根节点
	 */
	private BiTNode root ;
	
	
	/**
	 * 获取根节点
	 * @return
	 */
	public BiTNode getRoot() {
		return root;
	}

	/**
	 * 二叉排序树搜索
	 * @param root
	 * @param key
	 * @return
	 */
	private BiTNode searchBST(BiTNode root,int key){
		//查找不成功
		if(root==null){
			return null;
		}
		
		if(key<root.data){
			//key小于节点值，搜索左子树
			return searchBST(root.lChild,key);
		}else if(key>root.data){
			//key大于节点值，搜索右子树
			return searchBST(root.rChild,key);
		}else{
			//查找成功
			return root;
		}
	}
	
	/**
	 * 二叉排序树搜索
	 * @param key
	 * @return
	 */
	public BiTNode search(int key){
		return searchBST(root,key);
	}
	
	/**
	 * 插入节点
	 * @param root
	 * @param key
	 * @return
	 */
	private boolean insertBST(BiTNode root,int key){
		
		if(root.data<key && root.rChild!=null){
			
			// 节点值小于key并且有右孩子，则递归该节点的右孩子
			return insertBST(root.rChild,key);
			
		}else if(root.data>key && root.lChild!=null){
			
			// 节点值大于key并且有左孩子，则递归该节点的左孩子
			return insertBST(root.lChild,key);
			
		}else if(root.data<key && root.rChild==null){
			
			// 节点值小于key并且没有右孩子，则添加到该节点的右孩子
			BiTNode node = new BiTNode();
			node.data = key;
			root.rChild = node;
			return true;
			
		}else if(root.data>key && root.lChild==null){
			
			// 节点值大于key并且没有左孩子，则添加到该节点的左孩子
			BiTNode node = new BiTNode();
			node.data = key;
			root.lChild = node;
			return true;
		}else {
			return false;
		}
	}
	
	/**
	 * 插入节点
	 * @param key
	 * @return
	 */
	public boolean insert(int key){
		if(root==null){
			root = new BiTNode();
			root.data = key;
			return true;
		}else{
			return insertBST(root,key);
		}
	}
	
	/**
	 * 中序遍历二叉排序树(排序)
	 */
	private void inOrderTraverse(BiTNode root){
		if(root!=null){
			//遍历左子树
			inOrderTraverse(root.lChild);
			
			System.out.print(root.data+" ");
			
			//遍历右子树
			inOrderTraverse(root.rChild);
		}
		
	}
	
	/**
	 * 中序遍历二叉排序树(排序)
	 */
	public void inOrderTraverse(){
		inOrderTraverse(root);
	}
	
	/**
	 * 删除节点
	 * @param key
	 * @return
	 */
	public boolean delete(int key){
		BiTNode parent = root;
		BiTNode curr = root;
		boolean isLeftChild = true;
		
		//查找要删除的节点
		while(curr.data != key){
			parent = curr;
			
			if(key < curr.data){
				//key小于当前节点，往左子树找
				curr = curr.lChild;
				isLeftChild = true;
			}else{
				//key大于当前节点,往右子树找
				curr = curr.rChild;
				isLeftChild = false;
			}
			
			//如果子树为空，查找失败
			if(curr==null){
				return false;
			}
		}
		
		//如果要删除的节点没有孩子，直接删除
		if(curr.lChild==null && curr.rChild==null){
			if(curr==parent){
				//删除的是根节点
				root = null;
			}else if(isLeftChild==true){
				//删除的是非根节点左孩子
				parent.lChild = null;
			}else if(isLeftChild==false){
				//删除的是非根节点有孩子
				parent.rChild = null;
			}
			
			return true;
		}
		
		//如果要删除的节点没左子树,则右子树顶上
		if(curr.lChild==null){
			if(curr==parent){
				//删除的是根节点
				root = curr.rChild;
			}else if(isLeftChild==true){
				//删除的是非根节点左孩子
				parent.lChild = curr.rChild;
			}else if(isLeftChild==false){
				//删除的是非根节点有孩子
				parent.rChild = curr.rChild;
			}
			return true;
		}
		
		//如果要删除的节点没右子树,则左子树顶上
		if(curr.rChild==null){
			if(curr==parent){
				//删除的是根节点
				root = curr.lChild;
			}else if(isLeftChild==true){
				//删除的是非根节点左孩子
				parent.lChild = curr.lChild;
			}else if(isLeftChild==false){
				//删除的是非根节点有孩子
				parent.rChild = curr.lChild;
			}	
			return true;
		}
		
		//如果要删除的节点有左右子树，则找该节点中序遍历的前驱节点
		//将前驱节点移动到该节点的位置
		//前驱节点是左子树的最大节点，即最右节点
		BiTNode p = curr;
		BiTNode s = null;
		s = curr.lChild;
		while(s.rChild!=null){
			p=s;
			s=s.rChild;
		}
		
		if(p != curr){
			//前驱的父节点不是要删除的节点时
			//s为子树最大节点，肯定没有右子树
			p.rChild = s.lChild;
		}
		
		if(curr==parent){
			//删除的是根节点
			root = s;
			if(root!=curr.lChild){
				//消除环，当根节点的左孩子是前驱节点时
				//前驱节点替换后不用重复设置左孩子
				root.lChild=curr.lChild;
			}
			root.rChild=curr.rChild;
		}else if(isLeftChild==true){
			//删除的是非根节点左孩子
			parent.lChild = s;
			s.lChild = curr.lChild;
			s.rChild = curr.rChild;
		}else if(isLeftChild==false){
			//删除的是非根节点有孩子
			parent.rChild = s;
			s.lChild = curr.lChild;
			s.rChild = curr.rChild;
		}
		
		return true;
	}
	
	

	public static void main(String[] args) {
		BinarySortTree tree = new BinarySortTree();
		int[] seq = {70,67,105,46,100,115,99,104,110,103,108,112};
		for(int i :seq){
			tree.insert(i);
		}
		
		int data = 70;
		
		System.out.print("二叉排序树中序遍历：");
		tree.inOrderTraverse();
		
		System.out.println();
		
		System.out.print("二叉排序树搜索：");
		BiTNode node = tree.search(data);
		if(node!=null){
			System.out.println(node.data);
		}else{
			System.out.println("搜索失败");
		}
		
		
		System.out.println("二叉排序树删除节点："+data);
		tree.delete(data);
		System.out.print("二叉排序树中序遍历：");
		tree.inOrderTraverse();
		
	}

}
